import java.util.Stack;

class Solution {
    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效
     * 有效字符串需满足：
     * 1.左括号必须用相同类型的右括号闭合
     * 2.左括号必须以正确的顺序闭合
     * @param s 带括号的字符串
     * @return 判断该字符串中的括号是否匹配
     */
    public boolean isValid(String s) {
        //字符串为空,则括号匹配
        if(s.isEmpty()) return true;
        //使用辅助栈
        Stack<Character> stack=new Stack<Character>();
        //遍历字符串
        for(char c:s.toCharArray()){
            //若遇到左括号,则将其相应的右括号入栈
            if(c=='(') stack.push(')');
            else if(c=='{') stack.push('}');
            else if(c=='[') stack.push(']');
            //若遇到右括号,若此时栈为空或者栈顶元素与该右括号不匹配,则匹配失败
            else if(stack.empty()||c!=stack.pop()) return false;
        }
        //若栈为空,则括号匹配成功;若栈非空,则左括号多,括号不匹配
        return stack.isEmpty();
    }
}